Năm Kiến Nguyên đầu tiên (140 TCN) thời Hán Vũ đế, Trương Khiên làm Lang. Khi ấy có tù binh Hung Nô khai rằng Vương của nước Đại Nguyệt Chi bị Hung Nô chém đầu, dùng làm đồ đựng rượu. Triều đình tin lời ấy, muốn sai sứ đến Đại Nguyệt Chi đề nghị liên kết chống Hung Nô. Trương Khiên đáp ứng lời kêu gọi, nhận làm sứ giả đi Tây Vực. Năm Kiến Nguyên thứ 2 (139 TCN), ông cùng hơn trăm tình nguyện viên được kẻ nô bộc thuộc thị tộc Đường Ấp, dân tộc Hung Nô là Cam Phụ (còn gọi là Đường Ấp Phụ) dẫn đường, xuất phát từ Lũng Tây [2]. Giữa đường, Trương Khiên bị Hung Nô bắt được, giải đến nơi ở của Thiền vu [3], giam lỏng hơn 10 năm, đã lấy vợ sinh con nhưng vẫn không quên thân phận và nhiệm vụ của mình.

Trương Khiên nhân lúc người Hung Nô không đề phòng mà trốn đi, theo đường của nước Xa Sư [4], tiến vào nước Yên Kỳ [5], lại từ Yên Kỳ vượt sông Tháp Lý Mộc, đi qua các nước Quy Từ [6], Sơ Lặc [7], vượt qua Thông Lĩnh [8], đến được Đại Uyển [9], được người Đại Uyển đưa đến Khang Cư [10], cuối cùng đến được Đại Nguyệt Chi.

Nhưng lúc này Đại Nguyệt Chi sau khi dời đến lưu vực Amu Darya, chinh phục được nước láng giềng Đại Hạ [11], quyết định an cư lạc nghiệp, không muốn báo thù Hung Nô, lại cho rằng nhà Hán ở nơi xa xôi, không giúp ích gì. Trương Khiên ở lại hơn 1 năm, vào năm Nguyên Sóc đầu tiên (128 TCN) đành xin trở về.

Nhằm tránh gặp phải người Hung Nô, Trương Khiên đổi sang đường phía nam, vượt qua Thông Lĩnh, men theo phía bắc chân núi Côn Lôn mà đi, qua các nơi Toa Xa [12], Vu Điền [13], Thiện Thiện [14], tiến vào khu vực của người Khương. Nhưng lúc này người Khương đang quy phụ người Hung Nô, nên ông lại bị người Hung Nô bắt được, giam giữ hơn 1 năm. Năm Nguyên Sóc thứ 3 (126 TCN), Hung Nô có nội loạn, Trương Khiên thừa cơ đưa vợ con và trợ thủ Cam Phụ trốn về nhà Hán. Dựa vào báo cáo hết sức chi tiết của ông, Hán Vũ đế nắm được tình hình Tây Vực, rất hài lòng, phong Trương Khiên làm Thái trung đại phu, Cam Phụ làm Phụng sứ quân.